DROPS

Document

DOI: 10.4230/LIPIcs.CP.2023.9

Guiding Backtrack Search by Tracking Variables During Constraint Propagation

Authors: Gilles Audemard, Christophe Lecoutre, and Charles Prud'homme

Published in: LIPIcs, Volume 280, 29th International Conference on Principles and Practice of Constraint Programming (CP 2023)

Abstract

It is well-known that variable ordering heuristics play a central role in solving efficiently Constraint Satisfaction Problem (CSP) instances. From the early 80’s, and during more than two decades, the dynamic variable ordering heuristic selecting the variable with the smallest domain was clearly prevailing. Then, from the mid 2000’s, some adaptive heuristics have been introduced: their principle is to collect some useful information during the search process in order to take better informed decisions. Among those adaptive heuristics, wdeg/dom (and its variants) remains particularly robust. In this paper, we introduce an original heuristic based on the midway processing of failing executions of constraint propagation: this heuristic called pick/dom tracks the variables that are directly involved in the process of constraint propagation, when ending with a conflict. The robustness of this new heuristic is demonstrated from a large experimentation conducted with the constraint solver ACE. Interestingly enough, one can observe some complementary between the early, midway and late forms of processing of conflicts.

Cite as

Gilles Audemard, Christophe Lecoutre, and Charles Prud'homme. Guiding Backtrack Search by Tracking Variables During Constraint Propagation. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 9:1-9:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{audemard_et_al:LIPIcs.CP.2023.9,
  author =	{Audemard, Gilles and Lecoutre, Christophe and Prud'homme, Charles},
  title =	{{Guiding Backtrack Search by Tracking Variables During Constraint Propagation}},
  booktitle =	{29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
  pages =	{9:1--9:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-300-3},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{280},
  editor =	{Yap, Roland H. C.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.9},
  URN =		{urn:nbn:de:0030-drops-190461},
  doi =		{10.4230/LIPIcs.CP.2023.9},
  annote =	{Keywords: Variable Ordering Heuristics, Variable Weighting}
}

Document

DOI: 10.4230/LIPIcs.CP.2021.56

Solution Sampling with Random Table Constraints

Authors: Mathieu Vavrille, Charlotte Truchet, and Charles Prud'homme

Published in: LIPIcs, Volume 210, 27th International Conference on Principles and Practice of Constraint Programming (CP 2021)

Abstract

Constraint programming provides generic techniques to efficiently solve combinatorial problems. In this paper, we tackle the natural question of using constraint solvers to sample combinatorial problems in a generic way. We propose an algorithm, inspired from Meel’s ApproxMC algorithm on SAT, to add hashing constraints to a CP model in order to split the search space into small cells of solutions. By sampling the solutions in the restricted search space, we can randomly generate solutions without revamping the model of the problem. We ensure the randomness by introducing a new family of hashing constraints: randomly generated tables. We implemented this solving method using the constraint solver Choco-solver. The quality of the randomness and the running time of our approach are experimentally compared to a random branching strategy. We show that our approach improves the randomness while being in the same order of magnitude in terms of running time.

Cite as

Mathieu Vavrille, Charlotte Truchet, and Charles Prud'homme. Solution Sampling with Random Table Constraints. In 27th International Conference on Principles and Practice of Constraint Programming (CP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 210, pp. 56:1-56:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{vavrille_et_al:LIPIcs.CP.2021.56,
  author =	{Vavrille, Mathieu and Truchet, Charlotte and Prud'homme, Charles},
  title =	{{Solution Sampling with Random Table Constraints}},
  booktitle =	{27th International Conference on Principles and Practice of Constraint Programming (CP 2021)},
  pages =	{56:1--56:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-211-2},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{210},
  editor =	{Michel, Laurent D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2021.56},
  URN =		{urn:nbn:de:0030-drops-153477},
  doi =		{10.4230/LIPIcs.CP.2021.56},
  annote =	{Keywords: solutions, sampling, table constraint}
}

Search Results

Documents authored by Prud'homme, Charles

Guiding Backtrack Search by Tracking Variables During Constraint Propagation

Abstract

Cite as

Solution Sampling with Random Table Constraints

Abstract

Cite as

Thanks for your feedback!

Could not send message